package 最长重复子数组;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/17 11:57
 * @description:
 */
public class Solution2 {
    public int findLength(int[] nums1, int[] nums2) {
        // 子序列问题可以使用动态规划解决
        // ① dp数组及其下标含义：dp[i][j]表示nums1中以索引 i-1 结尾，nums2中以索引 j-1 结尾的最长子数字长度
        // ② 状态转移方程：nums[i-1] = nums[j-1] ? dp[i] = dp[i-1] + 1 : 0;
        // ③ dp数组的初始化： dp[0] = 0;
        // ④ 遍历顺序：从左上角遍历到右下角
        // ⑤ 举例推导dp数组：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
        //              index   0   1   2   3   4   5
        //                      0   0   0   0   0   0
        //                      0   0   0   1   0   0
        //                      0   0   1   0   2   0
        //                      0   1   0   0   0   3
        //                      0   0   0   0   0   0
        //                      0   0   0   0   0   0

        // 使用滑动数组
        int[] dp = new int[nums1.length + 1];
        int result = 0;
        System.out.println(Arrays.toString(dp));
        // 先遍历 nums2
        for (int i = 1; i <= nums2.length; i++) {
            // 再遍历 nums1
            for (int j = nums1.length; j >= 1; j--) {
                if (nums2[i - 1] == nums1[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else {
                    dp[j] = 0;
                }
                // 更新结果
                result = Math.max(dp[j], result);
            }
            System.out.println(Arrays.toString(dp));
        }
        return result;
    }
}
